package algorithms.leaning.class27;

import common.util.MyUtil;

/**
 * 主要用于字符串搜索，比如"gui"在"changgui"中的位置
 * 如果用传统的一一比对的方式时间复杂度是O(M * N)
 * KMP算法的时间复杂度是O(M + N)
 *
 * @author guichang
 * @date 2021/7/1
 */

@SuppressWarnings("all")
public class Code1_KMP_实现 {

    public static void main(String[] args) {
        String str1 = "changgui";
        String str2 = "gui";
        MyUtil.print(str1.indexOf(str2));
        MyUtil.print(indexOf(str1, str2));
    }

    /**
     * 时间复杂度 O(M + N)
     *
     * @param s1 原字符串，长度 M
     * @param s2 要搜索的字符串，长度 N
     * @return s2在s1中的位置
     */
    public static int indexOf(String s1, String s2) {
        if (s1 == null || s2 == null || s2.length() < 1 || s1.length() < s2.length()) {
            return -1;
        }
        char[] c1s = s1.toCharArray();
        char[] c2s = s2.toCharArray();
        // s1中当前搜索的位置
        int x = 0;
        // s2中当前比对的位置
        int y = 0;
        int[] next = nextArray(c2s);
        // 两者都不越界的情况下
        while (x < c1s.length && y < c2s.length) {
            // 两个位置相同同时走一步
            if (c1s[x] == c2s[y]) {
                x++;
                y++;
            }
            // y走到0位置了表示要换一个开头，所以x+1
            else if (next[y] == -1) {
                x++;
            }
            // 其他情况y往前走
            else {
                y = next[y];
            }
        }
        // x越界表示s1中遍历到头了还没找到
        // y越界表示s2遍历完了，s2能遍历完就说明找到了
        return y == c2s.length ? x - y : -1;
    }

    /**
     * 字符串s2中每个字符的前缀和后缀相等的最大长度
     * 比如changachangk中的k的位置11的值就是4
     *
     * @param c2s s2的字符数组
     * @return 对应最大长度数组
     */
    public static int[] nextArray(char[] c2s) {
        // 认为规定 0位置对应-1，1位置对应0
        if (c2s.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[c2s.length];
        next[0] = -1;
        next[1] = 0;
        // 目前在哪个位置上求next数组的值，从2开始
        int i = 2;
        // 当前是哪个位置的值在和i-1位置的字符比较
        int pi = 0;
        while (i < next.length) {
            // 配成功的时候
            if (c2s[i - 1] == c2s[pi]) {
                next[i++] = ++pi;
            }
            // cn还能往前跳的话就往上一个next位置跳
            else if (pi > 0) {
                pi = next[pi];
            }
            // cn跳到头了还是匹配不上就是0了
            else {
                next[i++] = 0;
            }
        }
        return next;
    }

}